//给定一个非负整数数组，a1, a2, ..., an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选
//择一个符号添加在前面。 
//
// 返回可以使最终数组和为目标数 S 的所有添加符号的方法数。 
//
// 
//
// 示例： 
//
// 输入：nums: [1, 1, 1, 1, 1], S: 3
//输出：5
//解释：
//
//-1+1+1+1+1 = 3
//+1-1+1+1+1 = 3
//+1+1-1+1+1 = 3
//+1+1+1-1+1 = 3
//+1+1+1+1-1 = 3
//
//一共有5种方法让最终目标和为3。
// 
//
// 
//
// 提示： 
//
// 
// 数组非空，且长度不会超过 20 。 
// 初始的数组的和不会超过 1000 。 
// 保证返回的最终结果能被 32 位整数存下。 
// 
// Related Topics 深度优先搜索 动态规划 
// 👍 508 👎 0

package com.leetcode.editor.cn;

import java.util.Arrays;

//Java：目标和
class P494TargetSum {
    public static void main(String[] args) {
        Solution solution = new P494TargetSum().new Solution();
        // TO TEST
        int[] nums = {1, 1, 1, 1, 1};
        System.out.println(solution.findTargetSumWays(nums, 3));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        int count = 0;

        public int findTargetSumWays(int[] nums, int S) {
//            help(nums, nums.length - 1, S);
//            return count;
            int[] dp = new int[2001];
            dp[nums[0] + 1000] = 1;
            dp[-nums[0] + 1000] += 1;
            for (int i = 1; i < nums.length; i++) {
                int[] next = new int[2001];
                for (int sum = -1000; sum <= 1000; sum++) {
                    if (dp[sum + 1000] > 0) {
                        next[sum + nums[i] + 1000] += dp[sum + 1000];
                        next[sum - nums[i] + 1000] += dp[sum + 1000];
                    }
                }
                dp = next;
            }
            return S > 1000 ? 0 : dp[S + 1000];
        }

        private void help(int[] nums, int end, int s) {
            if (nums.length == 1 && (s == nums[0] || s + nums[0] == 0)) {
                //nums[0]==0的话，那么+0和-0都符合，算两种
                if (s == 0) {
                    count += 2;
                } else {
                    count++;
                }
                return;
            }
            int[] ints = Arrays.copyOfRange(nums, 0, end);
            if (end >= 1) {
                help(ints, end - 1, s - nums[end]);
                help(ints, end - 1, s + nums[end]);
            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}